//
//  BST.hpp
//  BST_LCA
//
//  Created by chenyh on 2021/2/18.
//

#ifndef BST_hpp
#define BST_hpp
#include <iostream>
using namespace::std;
/**
 【例 2-7】 寻找二叉搜索树(BST)的最低公共祖先(LCA)。
 【分析】BST 树有一个很重要的性质，就是根结点的左子树结点都小于它，右子树结 点都大于它。这个性质被称为 BST 树的有序性。我们在寻找结点的最低公共祖先 LCA 时， 就可以利用这个性质，当我们从根结点开始查找，第一次遇到的结点值介于给定的两个结 点值之间时，当前结点就是我们要找的最低公共祖先结点。
 
 */
typedef struct Node
{
    int c;              //结点的值
    Node *LeftChild;    //左子树
    Node *RightChild;   //右子树
};
/**寻找最低的公共祖先结点*/
Node * findLCAInBST(Node *root,int a,int b) {
    if (root != NULL) {
        if (root->c > a &&& root->c < b || root->c < a && root) {
            return  root; //如果当前结点的值介于指定的两个结点值之间则返回
        }
        if (root->c < a && root->c < b) {
            //如果当前结点小于两个指定结点，则向它的右子结点遍历
            findLCAInBST(root->RightChild, a, b);
        }
        if (root->c > a && root->c > b) {
            //如果当前结点大于指定结点，则向左子结点遍历
            findLCAInBST(root->LeftChild, a, b);
        }
    }
}

/**
 例 2-8】给出一个数组，编写程序判定该数组是否是某个二叉查找树的后序遍历。
 【分析】假设存在某个数组{5、7、6、9、11、10、8}，这个数组的确是某个二叉查找 树的后序遍历结果。那么根据二叉查找树后序遍历的特点，我们可以推测出该树必然是如 图 2-16 所示的结构。
 由于后序遍历最后一个元素是该二叉树的根结点，所以 8 就 应该是整个二叉查找树的根结点。二叉查找树的性质是:左子树 的值小于根结点，右子树的值大于根结点。那么数组中比 8 小的 数就应该在左子树，比 8 大的数就应该在右子树。在判断的时候， 应该考虑从第一个比 8 大的数到 8 之前的所有元素都应该大于 8， 而前半部分的元素都应该小于 8，这样才符合二叉查找树的性质。 对左右子树递归地进行这种判断，如果所有元素都满足条件，那 么该数组就是某个二叉查找树的后序遍历结果。
 */
///////////////////////////
//验证一个数组是否是一个二叉查找树的后序遍历结果
//Return: 如果是则返回 true，否则返回 false
//////////////////////////
bool verifySquenceOfBST(int squence[],int length)
{
    if (squence == NULL || length <= 0) {
        return false;
    }
    //二叉查找树的根结点是数组的最后一个元素
    int root = squence[length - 1];
    //左子树的结点小于根结点
    int i = 0;
    for (; i<length-1; ++i) {
        if (squence[i] > root) {
            break;
        }
    }
    int j = i;
    //右子树的元素应该大于根结点
    for (; j<length-1; ++j) {
        if (squence[j] < root) {
            return false;
        }
    }
    
    //递归验证左子树是不是一个bst树
    bool left = true;
    if (i > 0) {
        left = verifySquenceOfBST(squence, i);
    }
    //递归验证右子树是不是一个bst树
    bool right = true;
    if (i < length - 1) {
        right = verifySquenceOfBST(squence+i, length - i - 1);
    }
    return (left && right); // 如果左右子树都满足，则返回true
    
}

#endif /* BST_hpp */
